#include <vector>

#include "tree.h"
using namespace std;
/**
 * @brief 从前序遍历和中序遍历中构建二叉搜索树
 *
 * @param preTraversal
 * @param midTraversal
 * @return TreeNode*
 */
TreeNode* createBST(vector<int>& preTraversal, vector<int>& midTraversal) {
  if (preTraversal.empty()) {
    return nullptr;
  }

  int rootValue = preTraversal.front();
  TreeNode* root = new TreeNode(rootValue);

  if (midTraversal.size() == 1) {
    return root;
  }

  int index;
  for (index = 0; index <= midTraversal.size(); ++index) {
    if (midTraversal.at(index) == rootValue) {
      break;
    }
  }

  vector<int> leftSubTreeMidTraversal(midTraversal.begin(),
                                      midTraversal.begin() + index);

  vector<int> rightSubTreeMidTraversal(midTraversal.begin() + index + 1,
                                       midTraversal.end());

  vector<int> leftSubTreePreTraversal(
      preTraversal.begin() + 1,
      preTraversal.begin() + leftSubTreeMidTraversal.size());

  vector<int> rightSubTreePreTraversal(
      preTraversal.end() - rightSubTreeMidTraversal.size(), preTraversal.end());

  createBST(leftSubTreePreTraversal, leftSubTreeMidTraversal);
  createBST(rightSubTreePreTraversal, rightSubTreeMidTraversal);

  return root;
}